from math import sqrt


class Solution:
    mid_list = [1, 1]

    def numDecodings(self, s: str) -> int:
        length = len(s)
        if not length:
            return 0
        res, count = 1, 0
        last_word = s[0]
        for word in s:
            if word == "1" or word == "2":
                count += 1
            elif word == "0":
                if count:
                    res *= self.solve_lianxu(count-1)
                    count = 0
                else:
                    return 0
            elif word in ["7", "8", "9"] and last_word == "2":
                if count:
                    res *= self.solve_lianxu(count)
                    count = 0
            elif count:
                res *= (self.solve_lianxu(count) + self.solve_lianxu(count-1))
                count = 0
            last_word = word
        if count:
            res *= self.solve_lianxu(count)
        return int(res)

    def solve_lianxu(self, count):
        if count < len(Solution.mid_list):
            return Solution.mid_list[count]
        # 算了一下差值是斐波拉契数列,
        mid_num = self.solve_lianxu(count-1) + \
                  (sqrt(5) / 5) * (((1 + sqrt(5)) / 2) ** (count - 1) - ((1 - sqrt(5)) / 2) ** (count - 1))
        Solution.mid_list.append(mid_num)
        return mid_num


a = Solution()
# print(a.numDecodings("12"))
# print(a.numDecodings("226"))
# print(a.numDecodings("26"))
# print(a.numDecodings("222"))
# print(a.numDecodings("22222"))
# print(a.numDecodings("222226"))
# print(a.numDecodings(""))
# print(a.numDecodings("546846561"))
# print(a.numDecodings("10"))
# print(a.numDecodings("100"))
print(a.numDecodings("27"))
print(a.numDecodings("227"))
print(a.numDecodings("17"))
# print(a.numDecodings("10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010"
#                      "101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101"
#                      "010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010"
#                      "10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101"
#                      "01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010"
#                      "1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010"
#                      "1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010"
#                      "10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101"
#                      "010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101"
#                      "010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101"
#                      "010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101"
#                      "010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101"
#                      "01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010"
#                      "10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101"
#                      "01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010"
#                      "10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101"
#                      "010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101"
#                      "01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010"
#                      "10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101"
#                      "01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010"
#                      "101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010"
#                      "101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010"))
